#pragma once
#include<iostream>

namespace MyBST
{
	template <class K>
	struct BSTNode
	{
		BSTNode<K>* _left;
		BSTNode<K>* _right;
		K _key;

		BSTNode(const K& key)
			:_left(nullptr)
			, _right(nullptr)
			,_key(key)
		{}
	};


	template<class K>
	class BST
	{
		typedef BSTNode<K> Node;
	public:
		BST(const K& key = 0)
		:_root(nullptr)
		{}

		bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}

			}
			cur = new Node(key);

			if (parent->_key > key)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}

		}

		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					cur = cur->_right;
				}
				else if(cur->_key < key)
				{
					cur = cur->_left;
				}
				else
				{
					return true;
				}
				return false;
			}
		}

		void InOrder()
		{
			PInOrder(_root);
			cout << endl;
		}


	private:
		void PInOrder(Node* root)
		{
			if (root == nullptr)
				return;

			PInOrder(root->_left);

			cout << root->_key;

			PInOrder(root->_right);
		}

		Node* _root;
	};
}